Wang Haihua
🍈 🍉🍊 🍋 🍌
所谓图, 概括地讲就是由一些点和这些点之间的连线组成的。定义为 $G=(V, E), V$ 是顶点的非空有限集合, 称为顶点集。 $E$ 是边的集合, 称为边 集。边一般用 $\left(v_{i}, v_{j}\right)$ 表示, 其中 $v_{i}, v_{j}$ 属于顶点集 $V$ 。
以下用 $|V|$ 表示图 $G=(V, E)$ 中顶点的个数, $|E|$ 表示边的条数。
如果图的边是没有方向的, 则称此图为无向图 (简称为图), 无向图的 边称为无向边 (简称边)。连接两顶点 $v_{i}$ 和 $v_{j}$ 的无向边记为 $\left(v_{i}, v_{j}\right)$ 或 $\left(v_{j}, v_{i}\right)$ 。
如果图的边是有方向 (带箭头) 的, 则称此图为有向图, 有向图的边称 为弧 (或有向边)。连接两顶点 $v_{i}$ 和 $v_{j}$ 的 弧记为 $\left\langle v_{i}, v_{j}\right\rangle$, 其中 $v_{i}$ 称为起点, $v_{j}$ 称为终点。显然此时弧 $\left\langle v_{i}, v_{j}\right\rangle$ 与弧 $\left\langle v_{j}, v_{i}\right\rangle$ 是不同的两条有向边。有向图的弧的起点称为弧头, 弧的终点称为弧尾。有 向图一般记为 $D=(V, A)$, 其中 $V$ 为顶点集, $A$ 为弧集。
定义1： 设 $e=(u, v)$ 是图 $G$ 的一条边，则称 $u 、 v$ 是 $e$ 的端点，并称 $u$ 与 $v$ 相邻, 边 $e$ 与顶点 $u$ (或 $v)$ 相关联。若两条边 $e_{i}$ 与 $e_{j}$ 有共同的端点, 则称 边 $e_{i}$ 与 $e_{j}$ 相邻; 称有相同端点的两条边为重边; 称两端点均相同的边为环; 称不与任何边相关联的顶点为孤立点。
定义2 无环且无重边的图称为简单图。
定义3 任意两点均相邻的简单图称为完全图。含 $n$ 个顶点的完全图 记为 $K_{n}$ 。
定义4 如果图 $G$ 的每条边 $e$ 都附有一个实数 $w(e)$, 则称图 $G$ 为赋权 图, 实数 $w(e)$ 称为边 $e$ 的权。 赋权图也称为网络。赋权图中的权 可以是距离、费用、时间、效益、成本等。 如果有向图 $D$ 的每条弧都被赋予了权, 则称 $D$ 为有向赋权图。
定义5
(1) 在无向图中, 与顶点 $v$ 关联的边的数目 (环算两次) 称 为 $v$ 的度, 记为 $d(v)$ 。
(2) 在有向图中, 从顶点 $v$ 引出的弧的数目称为 $v$ 的出度, 记为 $d^{+}(v)$, 从顶点 $v$ 引入的弧的数目称为 $v$ 的入度, 记为 $d^{-}(v), d(v)=d^{+}(v)+d^{-}(v)$ 称为 $v$ 的度。
度为奇数的顶点称为奇顶点, 度为偶数的顶点称为偶顶点
定理1 给定图 $G=(V, E)$, 所有顶点的度数之和是边数的 2 倍, 即 $$ \sum_{v \in V} d(v)=2|E| . $$ 推论1 任何图中奇顶点的总数必为偶数。
定义6 设 $G_{1}=\left(V_{1}, E_{1}\right)$ 与 $G_{2}=\left(V_{2}, E_{2}\right)$ 是两个图, 并且满足 $V_{1} \subset V_{2}$, $E_{1} \subset E_{2}$, 则称 $G_{1}$ 是 $G_{2}$ 的子图。如 $G_{1}$ 是 $G_{2}$ 的子图, 且 $V_{1}=V_{2}$, 则称 $G_{1}$ 是 $G_{2}$ 的 生成子图。
设 $W=v_{0} e_{1} v_{1} e_{2} \cdots e_{k} v_{k}$, 其中
$$ e_{i} \in E(i=1,2, \cdots, k), v_{j} \in V(j=0,1, \cdots, k) $$$e_{i}$ 与 $v_{i-1}$ 和 $v_{i}$ 关联, 称 $W$ 是图 $G$ 的一条道路, 简称路, $k$ 为路长, $v_{0}$ 为起点, $v_{k}$ 为终点; 各边相异的道路称为迹 (trail); 各顶点相异的道路称为轨道 (path), 记为 $P\left(v_{0}, v_{k}\right)$; 起点和终点重合的道路称为回路; 起点和终点重 合的轨道称为圈, 即对轨道 $P\left(v_{0}, v_{k}\right)$, 当 $v_{0}=v_{k}$ 时成为一个圈。称以两顶点 $u, v$ 分别为起点和终点的最短轨道之长为顶点 $u, v$ 的距离。
在无向图 $G$ 中, 如果从顶点 $u$ 到顶点 $v$ 存在道路, 则称顶点 $u$ 和 $v$ 是连通 的。如果图 $G$ 中的任意两个顶点 $u$ 和 $v$ 都是连通的, 则称图 $G$ 是连通图, 否则 称为非连通图。非连通图中的连通子图, 称为连通分支。 在有向图 $G$ 中, 如果对于任意两个顶点 $u$ 和 $v$, 从 $u$ 到 $v$ 和从到 $u$ 都存在 道路, 则称图 $G$ 是强连通图。
参考资料